package cn.edu.thu.thss.algorithm.structures;

/**
 * 不相交森林集合(并查集)的实现类
 * @author EricPai
 */
public class DisjointSet<T> {
	private DisjointSet<T> parent;
	private int rank;
	private T data;
	
	/**
	 * 创建新的集合
	 * @param data 集合中的数据
	 */
	public DisjointSet(T data) {
		this.data = data;
		rank = 0;
		parent = this;
	}
	
	/**
	 * 合并两个不相交森林集合
	 * @param anotherSet 另一个被合并的集合
	 */
	public void union(DisjointSet<T> anotherSet) {
		this.findSet().link(anotherSet.findSet());
	}
	
	/**
	 * 连接两个不相交森林集合，使用了按秩合并优化
	 * @param anotherSet 另一个被连接的集合
	 */
	private void link(DisjointSet<T> anotherSet) {
		if (rank > anotherSet.rank) {
			anotherSet.setParent(this);
		} else {
			this.parent = anotherSet;
			if (rank == anotherSet.rank) {
				anotherSet.rank++;
			}
		}
	}
	
	/**
	 * 查找这个集合的代表集合，使用了路径压缩
	 * @param anotherSet 另一个被连接的集合
	 */
	public DisjointSet<T> findSet() {
		DisjointSet<T> result = this;
		if (result != parent) {
			parent = parent.findSet();
			result = parent;
		}
		return result;
	}

	public DisjointSet<T> getParent() {
		return parent;
	}

	public void setParent(DisjointSet<T> parent) {
		this.parent = parent;
	}

	public int getRank() {
		return rank;
	}

	public void setRank(int rank) {
		this.rank = rank;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	@Override
	public String toString() {
		String result = "";
		if (parent != this) {
			result = "DisjointSet [parent=" + parent + ", rank=" + rank + ", data="
					+ data + "]";
		}
		return result;
	}
	
}
